package com.majie.leetcode.栈;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/valid-parentheses/
 * 给定一个只包括 '('，'{'，')'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 */

public class _20_有效的括号 {

    /**
     * 1 <= s.length <= 104
     * s 仅由括号 '()[]{}' 组成
     */
    public boolean isValid(String s) {
        while (s.contains("{}") || s.contains("[]") || s.contains("()")) {
            s = s.replace("{}", "");
            s = s.replace("[]", "");
            s = s.replace("()", "");
        }
        return s.isEmpty();
    }

    public static boolean isValid2(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c : chars) {
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else {
                if (stack.size() == 0) {
                    return false;
                }
                Character pop = stack.pop();
                if (c == '}' && pop != '{' || (c == ']' && pop != '[') || (c == ')' && pop != '(')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        boolean valid2 = isValid2("]");
        System.out.println(valid2);
    }
}
